package com.shm.duXiaoMan;

import java.util.*;

/**
 * 坚强的小昆虫
 * 时间限制： 3000MS
 * 内存限制： 589824KB
 * 题目描述：
 * 由于新冠肺炎疫情的爆发，小明养在宿舍的小昆虫已经很久很久都没有人管了。小昆虫已经饿的不行了，必须出来找东西吃，可是出来之后需要走出一个迷宫。小昆虫每次可以朝上、下、左、右四个方向之一走一步，且只要走出任意一条边界线即可逃出迷宫。这只小昆虫曾感染过X星的一种奇异病毒，目前还没有发现任何副作用，但是却拥有了一项特异功能——破坏障碍物。
 *
 * 假设小昆虫在一个N*M的迷宫中，"@"代表小昆虫的初始位置，"."代表可以通过的空地，"*"代表可以破坏的障碍物，"#"代表不可破坏的障碍物。请问小昆虫最少需要使用多少次特异功能才可以逃出迷宫？
 *
 *
 *
 * 输入描述
 * 多组数据，第1行有1个正整数T，表示有T组数据。（T<=100）
 *
 * 对于每组数据，第1行有两个整数N和M。(1<=N, M<=1000)
 *
 * 接着N行，每行有一个长度为M的字符串，表示N*M的迷宫。
 *
 * 输出描述
 * 输出一个整数，表示使用特异功能的最少次数。如果小昆虫不能走出迷宫，则输出-1。
 *
 *
 * 样例输入
 * 3
 *
 * 3 3
 * ###
 * #@*
 * ***
 * 3 4
 * ####
 * #@.*
 * **.*
 * 3 3
 * .#.
 * #@#
 * .#.
 * 样例输出
 * 1
 * 0
 * -1
 *
 */
public class Main2 {
    static int[][] direction = new int[][]{{1,0},{0,1},{-1,0},{0,-1}};
    static List<Integer> list = new ArrayList<>();
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
         String s1 = sc.nextLine();
        int i = Integer.parseInt(s1);
        for (int j = 0; j < i; j++) {
            String str = sc.nextLine();
            String[] ss = str.split(" ");
            int n = Integer.parseInt(ss[0]);
            int m = Integer.parseInt(ss[1]);
            String[] strs = new String[n];
            int x = 0;
            int y = 0;
            for (int k = 0; k < n; k++) {
                String str1 = sc.nextLine();
                strs[k] = str1;
                for (int p = 0; p < m; p++) {
                    if (str1.charAt(p)=='@'){
                        x = k;
                        y = p;
                        break;
                    }
                }
            }
            boolean[][] visited =new boolean[n][m];
            min(n,m,x,y,strs,visited,0);
            if (list==null){
                System.out.println(-1);
            }else {
                Collections.sort(list);
                System.out.println(list.get(0));
            }
        }
    }

    public static void min(int n,int m,int x,int y,String[] strs,boolean[][] visited,Integer count){
        if (x==0||y==0||x==n-1||y==m-1){
            list.add(new Integer(count));
            return;
        }
        int z = 0;
        for (int[] ints : direction) {
            x+=ints[0];
            y+=ints[1];
            if (x>=0&&x<n&&y>=0&&y<m&&!visited[x][y]){
                if (z==4){
                    list=null;
                    return;
                }
                if (strs[x].charAt(y)=='#') {
                    x -= ints[0];
                    y -= ints[1];
                    z++;
                    continue;
                }
                if (strs[x].charAt(y)=='.') {
                    visited[x][y]=true;
                    min(n,m,x,y,strs,visited,count);
                }
                if (strs[x].charAt(y)=='*'){
                    visited[x][y]=true;
                    count++;
                    min(n,m,x,y,strs,visited,count);
                }
            }else {
                x -= ints[0];
                y -= ints[1];
            }
        }
    }
}
